import java.util.*;


import java.util.*;
class Solution1 {

    public ArrayList<Integer> findOrder (int numProject, ArrayList<ArrayList<Integer>> groups) {
        if(groups.size()==0) return null;
        Map<Integer,List<Integer>> map=new HashMap<>();
        int n=groups.size();
        int[] ret=new int[numProject];
        for(int i=0;i<groups.size();i++){
            int a=groups.get(i).get(0),b=groups.get(i).get(1);
            if(!map.containsKey(b)){
                map.put(b,new ArrayList<Integer>());
            }
            ret[a]++;
            List<Integer> tt=map.get(b);
            tt.add(a);
            map.put(b,tt);
        }

        Queue<Integer> q=new LinkedList<>();
        ArrayList<Integer> list=new ArrayList<>();
        for(int i=1;i<numProject;i++){
            if(ret[i]==0) q.add(i);
        }
        while(!q.isEmpty()){
            int a=q.poll();
            list.add(a);
            List<Integer> A=map.getOrDefault(a,new ArrayList<>());
            for(int i=0;i<A.size();i++){
                int x=A.get(i);
                ret[x]--;
                if(ret[x]==0) q.add(x);

            }


        }
        for(int i=0;i<numProject;i++){
            if(ret[i]!=0) return null;
        }
        return list;
    }
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int lastStoneWeightII(int[] stones) {
        int n=stones.length;

        int sum1=0;
        for(int x:stones){
            sum1+=x;
        }
        int sum=sum1/2;
        int[][] dp=new int[n+1][sum+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=sum;j++){
                dp[i][j]=dp[i-1][j];
                if(j>=stones[i-1]){
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-stones[i-1]]+stones[i-1]);
                }
            }
        }
        return dp[n][sum];
    }

    public static void main(String[] args) {
        Stack<Character> st=new Stack<>();

        Solution s=new Solution();
        int[] stones={2,7,4,1,8,1};
        System.out.println(lastStoneWeightII(stones));
    }
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int v = in.nextInt();
        int[] tiji = new int[n];
        int[] value = new int[n];
        for (int i = 0; i < n; i++) {
            tiji[i] = in.nextInt();
            value[i] = in.nextInt();
        }
        int[][] dp = new int[n + 1][v + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= v; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= tiji[i - 1]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - tiji[i - 1]] + value[i - 1]);
                }
            }
        }
        System.out.println(dp[n][v]);
       Arrays.fill(dp[n], 0);
        for (int i = 1; i <= v; i++) dp[0][i] = -1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= v; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= tiji[i - 1]) {
                    if(dp[i - 1][j - tiji[i - 1]]!=-1)  dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - tiji[i - 1]] + value[i - 1]);
                }
            }
        }
        System.out.println(dp[n][v]);
    }
}